package day_2022_7_to_8.day48;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

/**
 * @author haomin
 * @date 2022/07/23 20:25
 **/


public class Day8_3_Num21_MergeTwoLists {
    // 方法一：while循环
    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null) return list2;
            if(list2 == null) return list1;

            ListNode dummyHead = new ListNode(-1);
            ListNode tail = dummyHead;
            while(list1 != null && list2 != null){
                if(list1.val <= list2.val){
                    tail.next = list1;
                    tail = tail.next;
                    list1 = list1.next;
                }else {
                    tail.next = list2;
                    tail = tail.next;
                    list2 = list2.next;
                }
            }
            if(list1 == null) tail.next = list2;
            if(list2 == null) tail.next = list1;

            return dummyHead.next;
        }
    }

    // 方法二：递归
    class Solution2 {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1 == null) return list2;
            if(list2 == null) return list1;

            if(list1.val <= list2.val){
                list1.next = mergeTwoLists(list1.next,list2);
                return list1;
            }else {
                list2.next = mergeTwoLists(list1,list2.next);
                return list2;
            }
        }
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        if(list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next,list2);
            return list1.next;
        }else {
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}